package JZ_LC;

import java.util.ArrayList;
import java.util.Stack;

public class T_06_从尾到头打印链表 {
    //方法一：递归
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        helper(head, list);

        //将list转为题目需要的int[]
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    private void helper(ListNode head, ArrayList<Integer> res) {
        if (head == null) {
            return;
        }
        helper(head.next, res);
        res.add(head.val);
    }

    //方法二：反转链表法
    public int[] reversePrint2(ListNode head) {
        ListNode res = reverse_rec(head);
        //ListNode res = reverse(head);
        int len = 0;
        ListNode temp = res;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = res.val;
            res = res.next;
        }
        return arr;
    }

    //递归进行反转
    private ListNode reverse_rec(ListNode head) {
        //head==null，只在一开始head就为null时起作用
        //其他情况都是在判断 head.next==null
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse_rec(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //非递归进行链表反转
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    //方法三：栈方法（不推荐）
    public int[] reversePrint3(ListNode head) {
        Stack<Integer> s = new Stack<>();
        while (head != null) {
            s.push(head.val);
            head = head.next;
        }
        int len = s.size();
        int[] arr = new int[len];
        //注意这里不能写成 i < s.size()，因为s.pop()后，s的size就变化了。
        for (int i = 0; i < len; i++) {
            arr[i] = s.pop();
        }
        return arr;
    }
}
